package suanfa

type Node struct {
	Data interface{}
	next *Node
}

type List struct {
	Size uint64 // 车辆数量
	Head *Node  // 车头
	Tail *Node  // 车尾
}

// 初始化链表
func (list *List) Init() {
	(*list).Size = 0
	(*list).Head = nil // 没有车头
	(*list).Tail = nil // 没有车尾
}

// 链表中增加元素
func (list *List) Append(node *Node) bool {
	if node == nil {
		return false
	}

	(*node).next = nil // 将新元素放入单链表中
	if (*list).Size == 0 {
		(*list).Head = node
	} else {
		oldTail := (*list).Tail
		oldTail.next = node
	}
	// 调整尾部位置，及链表元素数量
	(*list).Tail = node // node成为新的尾部
	(*list).Size++      // 元素数量增加

	return true
}

func (list *List) Insert(i uint64, node *Node) bool {
	if node == nil || i > (*list).Size || (*list).Size == 0 {
		return false
	}

	if i == 0 { //插入的第一个
		(*node).next = (*list).Head
		(*list).Head = node
	} else {
		// 找到第一个元素
		preItem := (*list).Head
		for j := 0; j < int(i); j++ { // 数前面i个元素
			preItem = (*preItem).next
		}
		// 原来元素放到新元素后面， 新元素放到前一个元素后面
		(*node).next = (*preItem).next
		(*preItem).Data = preItem
	}

	(*list).Size++

	return true
}
